
#include "scheduler.h"

static ready_queue_t ready_queue;
static uint32_t in_ready_queue[MAX_PRIORITY]; /* this array will count the number of processes of each priority level in the queue */

/* initializes the scheduler's data structures */
void initialize_scheduler(){
  ; //nothing to do for now
}

/* inserts pcb in the ready queue */
int32_t insert_ready_queue(PCB* pcb){
  int i,j;
  int priority;
  int count = ready_queue.count;
  if(count == NUMBER_MAX_PROCESSES) 
    //the queue is full
    return 0;
  
  priority = pcb_get_priority(pcb);
  for(i=0; i < count && priority >= pcb_get_priority(ready_queue.queue[i]) ; i++);
  // i now points to the place where pcb must be inserted
  // we have to move the others pcb first
  for(j=count-1;j>=i;j--)
    ready_queue.queue[j+1] = ready_queue.queue[j];
  // we can insert our pcb
  ready_queue.queue[i] = pcb;
  // there is one more element in the queue
  ready_queue.count++;
  //there is one more process with this priority
  in_ready_queue[priority]++;
  return 1;
}

/* removes pcb from the ready queue */
int32_t remove_ready_queue(PCB* pcb){
  int i,j;
  int pid;
  int count = ready_queue.count;
  if(count == 0)
    //the queue is empty
    return 0;
  
  pid = pcb_get_pid(pcb);
  for(i=0;i<count && pid != pcb_get_pid(ready_queue.queue[i]);i++);
  // if i == count, we didn't find the correct PCB in the ready queue
  if(i==count)
    return 0;
  else{
    //the PCB has been found at index i
    for(j=i;j<count-1;j++)
      ready_queue.queue[j] = ready_queue.queue[j+1];
    //there is one less element in the queue
    ready_queue.count --;
    //there is one less element with this priority
    in_ready_queue[pcb_get_priority(pcb)]--;
    /* if this process was implicated in a round, we need to change the index */
    if(round_robin && pcb_get_priority(pcb) == pcb_get_priority(running))
      round_robin_index --;
  }
  return 1;
}

/* Corrects the value in the array in_ready_queue after change_priority has been called */
void do_change_priority(int32_t old, int32_t new) {
  in_ready_queue[old]--;
  in_ready_queue[new]++;
  sort_ready_queue();
}

/* returns the first element of the ready queue */
PCB* get_first(){
  if(!ready_queue.count)
    //the queue is empty
    return NULL;
  else
    return ready_queue.queue[0];
}

/* returns the element at index n in the ready queue */
PCB* get_by_index(int n){
  int count = ready_queue.count;
  
  if(n < count)
    // there is something at the requested index
    return ready_queue.queue[n];
  else 
    //there is nothing at the requested index
    return NULL;
}

/* returns a pointer to the running PCB */
PCB* get_running(){
  return running;
}

/* sorts the ready queue by priority (highest priority first) */
void sort_ready_queue(){
  int unsorted = 1;
  int i,j;
  int count = ready_queue.count;
  PCB* tmp;
  
  for(i=0; (i< count) && unsorted; i++){
    unsorted = 0;
    for(j=1;j< (count-i); j++){
      if(pcb_get_priority(ready_queue.queue[j-1]) > pcb_get_priority(ready_queue.queue[j])){
	tmp = ready_queue.queue[j-1];
	ready_queue.queue[j-1] = ready_queue.queue[j];
	ready_queue.queue[j] = tmp;
	unsorted = 1;
      }
    }
  }
}

/* chooses the next process to be scheduled */
PCB* choose_next_process(){
	/* gets the highest priority process */
	PCB* first = get_first();
	if(first == NULL)
	  //the queue is empty
	  return NULL;

	if(round_robin){
		/* scheduler in RR mode */
		/* gets the number of processes involved in the round */
	        int count = in_ready_queue[pcb_get_priority(running)];
		/* does the RR mode need to continue? Two cases:
			- count < 2
			- a process (first) with a higher priority has arrived
		*/
		if(count < 2 || pcb_get_priority(first) < pcb_get_priority(running)){
			round_robin = 0;
		}else{
			/* RR still in use */
			/* get the index of the next process to run */
			round_robin_index = (round_robin_index +1)%count;
			/* round_robin_index now indicates the next process to run */
			return get_by_index(round_robin_index); 
		}
	}	
	/* the RR mode has been deactivated or is not used,
	   we must run the process with highest priority, that is first */
	/* is there other processes with the highest priority? */
	if(in_ready_queue[pcb_get_priority(first)] > 1){
		/* Round Robin mode */
		round_robin = 1;
		/* this first process in the queue is executing */
		round_robin_index = 0;
	}
	return first;
}

/* selects the next process to run and tells the dispatcher to give it the CPU */
void schedule(){
  PCB* next = choose_next_process();
  if(next != NULL){
    //  next must be scheduled. running has been saved by the exception handler.
    if(running != NULL && pcb_get_state(running) == RUNNING_STATE)
      pcb_set_state(running, READY_STATE);
    pcb_set_state(next, RUNNING_STATE);
  }
  running = next;
}

